/*
 * @lc app=leetcode.cn id=64 lang=java
 *
 * [64] 最小路径和
 */

// @lc code=start
// 每次更新每行每列走到这一步的最小值？
class Solution {
    public int minPathSum(int[][] grid) {
        int n = grid[0].length ,m = grid.length;//n是宽，m是高。题目限定m,n至少为1
        
        //先初始化第一行和第一列
        for(int i=1; i<m ;i++){//第一列
            grid[i][0]+=grid[i-1][0];
        }
        for(int i=1;i<n ;i++){//第一行
            grid[0][i]+=grid[0][i-1];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                grid[i][j] +=Math.min(grid[i-1][j], grid[i][j-1]);
            }
        }
        return grid[m-1][n-1];
    }
}
// @lc code=end

